// 二叉搜索树中第K小的元素 - 二叉搜索树中第K小的元素 - 力扣（LeetCode）
// 作者：LeetCode-Solution
// 链接：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/solution/er-cha-sou-suo-shu-zhong-di-kxiao-de-yua-8o07/
//     来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。



// 方法一：中序遍历
// 二叉搜索树具有如下性质：
// 结点的左子树只包含小于当前结点的数。
// 结点的右子树只包含大于当前结点的数。
// 所有左子树和右子树自身必须也是二叉搜索树。
// 二叉树的中序遍历即按照访问左子树——根结点——右子树的方式遍历二叉树；在访问其左子树和右子树时，我们也按照同样的方式遍历；直到遍历完整棵树。

// var kthSmallest = function(root, k) {
//   const stack = [];// 初始化一个栈
//   while (root != null || stack.length) {// 当根节点不为空或者栈不为空时
//     while (root != null) {// 当根节点不为空时
//       stack.push(root);// 将根节点入栈
//       root = root.left;// 将根节点的左子树赋值给根节点
//     }
//     root = stack.pop();// 将栈顶元素出栈
//     --k;// 减少k
//     if (k === 0 ) {// 当k为0时
//       break;// 结束循环
//     }
//     root = root.right;// 将根节点的右子树赋值给根节点
//   }
//   console.log(stack);
//   return root.val;// 返回根节点的值
// };
// const root = {
//   val: 3,
//   left: {
//     val: 1,
//     left: null,
//     right: null
//   },
//   right: {
//     val: 4,
//     left: {
//       val: 2,
//       left: null,
//       right: {
//         val: 5,
//         left: null,
//         right: {
//           val: 6,
//           left: null,
//         }
//       }
//     }
//   }
// }
// console.log(kthSmallest(root, 4));

//
var kthSmallest = function(root, k) {
 const stack = [];// 初始化一个栈
  while (root!=null||stack.length ){
    while(root!=null){
      stack.push(root);
      root = root.left;
    }
    root =stack.pop();//找到当前的根节点
    k--;
    if(k===0){
      break;
    }
    root = root.right
  }
  return root.val
};
const root = {
  val: 3,
  left: {
    val: 1,
    left: null,
    right: null
  },
  right: {
    val: 4,
    left: {
      val: 2,
      left: null,
      right: {
        val: 5,
        left: null,
        right: {
          val: 6,
          left: null,
        }
      }
    }
  }
}
console.log(kthSmallest(root, 4));
